package algorithms.leecode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Optional;
import java.util.Stack;

public class Au84 {
    public static void main(String[] args) {
//        Optional.ofNullable("2ww").orElse("ww");
//        Integer i = 1 << 11;
//        System.err.println(i);
        System.err.println(new Au84().largestRectangleArea(new int[]{2,1,2}));
    }
    public int largestRectangleArea1(int[] heights) {
        int len = heights.length;
        if (len == 0) {
            return 0;
        }
        if (len == 1) {
            return heights[0];
        }

        int area = 0;
        int[] newHeights = new int[len + 2];
        for (int i = 0; i < len; i++) {
            newHeights[i + 1] = heights[i];
        }
        len += 2;
        heights = newHeights;

        Deque<Integer> stack = new ArrayDeque<>();
        stack.addLast(0);

        for (int i = 1; i < len; i++) {
            while (heights[stack.peekLast()] > heights[i]) {
                int height = heights[stack.removeLast()];
                int width  = i - stack.peekLast() - 1;
                area = Math.max(area, width * height);
            }
            stack.addLast(i);
        }
        return area;
    }
    public int largestRectangleArea(int[] heights) {
        if (heights.length == 0) {
            return 0;
        }
        if (heights.length == 1) {
            return heights[0];
        }
        int reMax = 0;
        int len = heights.length;
        Stack<Integer> stk = new Stack<>();
        int[] newHeights = new int[len + 2];
        for (int i = 0; i < len; i++) {
            newHeights[i + 1] = heights[i];
        }

        heights = newHeights;
        for (int i = 0; i < heights.length; i++) {
            while (!stk.isEmpty() && heights[stk.peek()] > heights[i]) {
                int left = stk.pop();
                int h = heights[left];
                reMax = Math.max(reMax,h * (i - stk.peek() - 1));
            }
            stk.push(i);
        }

        return reMax;
    }
}
